package org.example.leetcpde;

import org.junit.jupiter.api.Test;

public class MergeKLists
        implements IListNode {

    @Test
    void run() {
        //        int[][] lists = {{1, 4, 5}, {1, 3, 4}, {2, 6}};
        int[][] lists = {{}, {-1, 5, 11}, {}, {6, 10}};
        ListNode[] listNodes = new ListNode[lists.length];

        for (int i = 0; i < lists.length; i++) {
            ListNode next = null;
            int[] list = lists[i];
            for (int j = list.length - 1; j >= 0; j--) {
                ListNode listNode = new ListNode(list[j]);
                listNode.next = next;
                next = listNode;
            }
            listNodes[i] = next;
        }

        ListNode listNode = merge(listNodes, 0, listNodes.length - 1);
        for (; listNode != null; listNode = listNode.next) {
            System.out.println(listNode.val);
        }
    }

    ListNode merge(ListNode[] listNodes,
                   int left,
                   int right) {

        if (left == right) {
            return listNodes[left];
        }

        if (left > right) {
            return null;
        }

        int mid = (left + right) >> 1;
        ListNode merge = merge(listNodes, left, mid);
        ListNode merge1 = merge(listNodes, mid + 1, right);
        return mergeTwoLists(merge, merge1);
    }

    //    ListNode mergeTwoLists(ListNode a,
    //                           ListNode b) {
    //        if (a == null) {
    //            return b;
    //        }
    //
    //        if (b == null) {
    //            return a;
    //        }
    //
    //        ListNode head = new ListNode(0);
    //        ListNode tail = head;
    //
    //        for (; a != null && b != null; ) {
    //            if (a.val <= b.val) {
    //                tail.next = a;
    //                a = a.next;
    //            } else {
    //                tail.next = b;
    //                b = b.next;
    //            }
    //
    //            tail = tail.next;
    //        }
    //
    //        tail.next = a != null ? a : b;
    //        return head.next;
    //    }


    public ListNode mergeTwoLists(ListNode a,
                                  ListNode b) {
        if (a == null) {
            return b;
        }

        if (b == null) {
            return a;
        }

        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        for (; aPtr != null && bPtr != null; ) {
            if (aPtr.val <= bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }

            tail = tail.next;
        }

        tail.next = aPtr != null ? aPtr : bPtr;
        return head.next;
    }
}
